/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode *getNewNode(int key) {
    struct TreeNode *p = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    p->val = key;
    p->left = p->right = NULL;
    return p;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if (preorderSize == 0) return NULL;
    int key = preorder[0], n = preorderSize;
    struct TreeNode *root = getNewNode(key);
    int ind = 0;
    while (inorder[ind] != key) ind++;
    root->left = buildTree(preorder + 1, ind, inorder, ind);
    root->right = buildTree(preorder + ind + 1, n - ind - 1, inorder + ind + 1, n - ind - 1);
    return root;
}
